class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (needle == NULL || haystack == NULL) {
            return NULL;
        }
        int n = strlen(haystack);
        int m = strlen(needle);
        if (n < m) {
            return NULL;
        } else if (m == 0) {
            return haystack;
        }

        vector<int> next(m);
        next[0] = 0;
        for (int i = 1; i < m; ++i) {
            int k = next[i - 1];
            while (k > 0 && needle[k] != needle[i]) {
                k = next[k - 1];
            }
            if (needle[k] == needle[i]) {
                next[i] = k + 1;
            } else {
                next[i] = 0;
            }
        }

        int cur = 0;
        for (int i = 0; i < n; ++i) {
            while (cur > 0 && needle[cur] != haystack[i]) {
                cur = next[cur - 1];
            }
            if (needle[cur] == haystack[i]) {
                ++cur;
            }
            if (cur == m) {
                return haystack + i - m + 1;
            }
        }
        return NULL;
    }
};
